Due to the huge size of the raw digital video data (or image sequences) used by present day multimedia applications, compression must be applied to such data so that it can be transmitted and stored. There have been many important video compression standards, including the ISO/IEC MPEG-1, MPEG-2, MPEG-4 standards and the ITU-T H.261, H.263, H.264 standards. The ISO/IEC MPEG-1/2/4 standards are used extensively by the entertainment industry to distribute movies, digital video broadcast including video compact disk or VCD (MPEG-1), digital video disk or digital versatile disk or DVD (MPEG-2), recordable DVD (MPEG-2), digital video broadcast or DVB (MPEG-2), video-on-demand or VOD (MPEG-2), high definition television or HDTV in the US (MPEG-2), etc. The MPEG-4 standard is more advanced than MPEG-2 and can achieve high quality video at lower bit rate, making it very suitable for video streaming over internet, digital wireless network (e.g. 3 G network), multimedia messaging service (MMS standard from 3 GPP), etc. MPEG-4 is accepted into the next generation high definition DVD (HD-DVD) standard and the MMS standard. The ITU-T H.261/3/4 standards are designed for low-delay video phone and video conferencing systems. The early H.261 standard was designed to operate at bit rates of p*64 kbit/s, with p=1, 2, . . . , 31. The later H.263 standard is very successful and is widely used in modern day video conferencing systems, and in video streaming in broadband and in wireless network, including the multimedia messaging service (MMS) in 2.5 G and 3 G networks and beyond. The latest standard, H.264 (also called MPEG-4 Version 10, or MPEG-4 AVC) is currently the state-of-the-art video compression standard. It is so powerful that MPEG decided to jointly develop with ITU-T in the framework of the Joint Video Team (JVT). The new standard is called H.264 in ITU-T and is called MPEG-4 Advance Video Coding (MPEG-4 AVC), or MPEG-4 Version 10. H.264 is used in the HD-DVD standard, Direct Video Broadcast (DVB) standard and probably the MMS standard. Based on H.264, a related standard called the Audio Visual Standard (AVS) is currently under development in China. AVS 1.0 is designed for high definition television (HDTV). AVS-M is designed for mobile applications. H.264 has superior objective and subjective video quality over MPEG-1/2/4 and H.261/3. The basic encoding algorithm of H.264 [1] is similar to H.263 or MPEG-4 except that integer 4=4 discrete cosine transform (DCT) is used instead of the traditional 8=8 DCT and there are additional features include intra prediction mode for I-frames, multiple block sizes and multiple reference frames for motion estimation/compensation, quarter pixel accuracy for motion estimation, in-loop deblocking filter, context adaptive binary arithmetic coding, etc.
Motion Estimation is the core part in most video compression standards such as MPEG-1/2/4 and H.261/3/4, to exploit temporal redundancy, so its performance directly affects the compression efficiency, subjective video quality and coding speed of a video coding system.
In block matching motion estimation (BMME), the most common measure of the distortion between the current block and the reference block in ME is the sum of absolute difference (SAD), for an N×N block, defined as:
      SAD    ⁡          (              mvx        ,        mvy            )        =            ∑                        m          =          0                ,                  n          =          0                            N        -        1              ⁢                                              F            t                    ⁡                      (                                          x                +                m                            ,                              y                +                n                                      )                          -                              F                          t              -              1                                ⁡                      (                                          x                +                m                +                mvx                            ,                              y                +                n                +                mvy                                      )                                    where Ft is the current frame, Ft−1 is the reference frame and (mvx, mvy) represents the current motion vector (MV). For a frame with width=X, height=Y, and block size=N×N, the total number of search points at which the SAD needs to be evaluated in order to find the optimum motion vector in a search range equal to ±W is:
            (              X        N            )        ⁢          (              Y        N            )        ⁢                  (                              2            ⁢            W                    +          1                )            2        ,which is equal to 1673100 for X=352, Y=288, N=16 and W=32. This is a huge number that can consume huge computation power in a video encoder. Many fast algorithms [2]-[9] have been proposed to reduce the number of search points in ME, such as Three-Step Search (TSS) [11], 2D log Search [12], New Three-Step Search (NTSS) [3], MVFAST [7], and PMVFAST [2]. MVFAST and PMVFAST significantly outperform the first three algorithms as they perform center-biased ME using a median motion vector predictor as a search center and hence reduce the number of bits for MV encoding by smoothing the motion vector field.
The PMVFAST algorithm (which is a significant improvement on MVFAST and other fast algorithms, and thus was accepted into MPEG standard [10]) initially considers a set of MV predictors, including median, zero, left, top, top-right and previous co-located MV predictor. FIG. 1 illustrates the locations of the locations of the current block, the left block, the top block, the topRight block, the topRightRight block, and the right block (which is a “future block”, i.e. a block which is processed after the current block). It computes the SAD cost for each prediction. In later developments, PMVFAST was modified to compute the RD (Rate Distortion) cost [13] instead of the SAD cost using the following cost function:J(m,λmotion)=SAD(s,c(m))+λmotion(R(m−p))  (1)where s is the original video signal and c is the reference video signal, m is the current MV, p is the median MV predictor of the current block, λmotion is a Lagrange multiplier and R(m−p) represents the bits used to encode the motion information. The next step in PMVFAST is to select the MV predictor that has minimum cost, and perform large or small diamond searches based on the value of the minimum cost obtained from the MV predictors.
A separate but important issue in defining current video coding standards, is the use of subpixel motion vectors including half-pixel, quarter-pixel or perhaps even ⅛-pixel motion vectors, which give more accurate description of motion and can give a PSNR gain of about 1 dB over integer-pixel motion estimation. With half-pixel precision, motion vectors can take on uniformly-spaced location values such as 0.0, 0.5, 1.0, 1.5, 2.0, etc. With quarter-pixel precision, motion vectors can take on location values such as 0.00, 0.25, 0.50, 0.75, 1.00, 1.25, 1.50, 1.75, 2.00, etc. With ⅛ pixel precision, motion vectors can take on location values such as 0.000, 0.125, 0.250, 0.375, 0.500, 0.625, 0.750, 0.875, 1.000, 1.125, 1.250, 1.375, 1.500, 1.625, 1.750, 1.875, 2.000, etc.
It is well known that motion vector distribution tends to be center-biased, which means that motion vectors tend to be very close to (0, 0). This is shown in FIG. 6 (a), which shows the motion vector distribution in Foreman sequence using the Full Search (FS) algorithm for (0,0) MV. In addition, as shown in FIG. 6(b), the motion vector distribution is also biased towards the median predictor (medianMV) which is the median of the motion vectors for the left block, top block and topright block shown in FIG. 1. In addition, the motion vector is also biased towards the adjacent motion vectors (leftMV, topMV, topRightMV) in the current frame and the collocated motion vector (preMV) in the previous frame, as shown in FIG. 6(c). It is also biased towards the bottom-right motion vector (preBottomRightMV) in the previous frame, as shown in FIG. 6(d). These can all be considered predictors for the motion vector of the current vector and they can be used in PMVFAST.